A packet-processing device, like a switch microchip, usually needs to buffer the packets into a packet buffer memory (PM) having one or more banks while the device processes them. The size of some packets (for example Ethernet packets) is not known up-front, so the device needs to start storing the packet into the packet buffer without knowing how large the packet is. Moreover, packets arrive at the device in an interleaved fashion, so the device is simultaneously storing several incoming packets into the packet buffer. The state-of-the-art solution to store the packet in the device's packet memory is to assign multiple chunks (called pages) of packet memory to each packet, rather than a single big chunk. With this scheme, the packet is not stored consecutively in the banks of the packet memory, but rather scattered in one or more pages throughout multiple banks of the packet memory. As a result, a linked list of all the pages (and therefore banks) that a particular packet uses needs to be maintained in the switch; this linked list is then traversed to locate and read out the packet from the packet memory for transmission.
In a type of packet traffic known as broadcast traffic, all of the output ports of the device are requested to output the same packet data. Similarly, in a type of packet traffic known as multicast traffic, a plurality (but not all) of the output ports of the device are requested to output the same packet data. Therefore, for such traffic all these output ports will request the packet memory for the same packet data. This can create performance issues in the device because it causes a large number of output ports request for the same data at roughly the same time. Specifically, when this happens often a small number of banks of the packet memory will need to serve all the requests while the other banks remain idle. As a result, although some of the output ports would get the data fast, others would need to wait a relatively long time to obtain the data because the a small subset of banks needs to serialize all the requests from the output ports due to the usually small number of read ports per bank.
This waiting time for the data has two undesirable consequences. If the data corresponds to the start of the packet, the transmission of the whole packet will be delayed. This implies a degradation in bandwidth of the port since it is waiting to send data when it actually could be sending data. If the data corresponds to the middle of the packet and some of the data of the packet has already been transmitted, the output port fails to transmit at the required rate and incurs into an underrun error. This is more severe than the performance degradation described above because the packet is transmitted with an error and the receiver will have to discard the packet, causing in some cases the costly retransmission of the packet. The second case described above is most common when the switch is working in cut-thru mode. In this mode, all the output ports that need to transmit the packet will do so at roughly the same time because they are instructed to transmit the packet as soon as possible without waiting for the entire packet to be received.